/* 
利用一个栈实现以下递归函数的非递归计算
Pn(x) = 1, n=0时
Pn(x) = 2x, n=1时
Pn(x) = 2xPn-1(x) - 2(n-1)Pn-2(x), n>1时
*/
#include <iostream>
using namespace std;
#define maxsize 50

// 计算函数Pn(x)的值
double fun2(int n,double x){
  
  // 要迭代top次，才能确定函数的值
  int top=n-2;
  
  // 数组，存储 Pn(x) Pn-1(x) ... P1(x) P0(x)
  double st[n];
  
  // P0(x)的值
  double fv1=1;
  
  // P1(x)的值
  double fv2=2*x;
  
  // n从2开始
  n=2;
  
  // 循环迭代
  while(top>=0){
    
    // 根据 Pn-1(x)、Pn-2(x) 计算 Pn(x)
    st[top]=2*x*fv2-2*(n-1)*fv1;
    
    // 更新 Pn-2(x)
    fv1=fv2;
    
    // 更新 Pn-1(x)
    fv2=st[top];
    
    // 更新n
    ++n;
    
    // 更新存储位置
    top--;
  }
  
  // n=0时，函数值为1
  if (n == 0)
    return fv1;
  
  // 返回 Pn(x)
  return fv2;
}

int main()
{
  int n=3;
  
  // 输出函数结果
  cout << fun2(n, 3);
  return 0;
}
